package leetcode.editor.cn;
//给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [3,2,3]
//输出：[3] 
//
// 示例 2： 
//
// 
//输入：nums = [1]
//输出：[1]
// 
//
// 示例 3： 
//
// 
//输入：nums = [1,2]
//输出：[1,2] 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 5 * 10⁴ 
// -10⁹ <= nums[i] <= 10⁹ 
// 
//
// 
//
// 进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。 
//
// Related Topics 数组 哈希表 计数 排序 👍 723 👎 0


import java.util.*;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution273 {
    public List<Integer> majorityElement1(int[] nums) {
        int length = nums.length;
        int threshold = length / 3;
        Arrays.sort(nums);
        int count = 0;
        Integer pre = null;
        HashSet<Integer> res = new HashSet<>();
        for (int num : nums) {

            if (pre == null || pre != num) {
                pre = num;
                count = 0;
            }

            count++;

            if (count > threshold) {
                res.add(num);
            }
        }
        return new LinkedList<>(res);
    }


    public List<Integer> majorityElement2(int[] nums) {
        int threshold = nums.length / 3;
        HashSet<Integer> res = new HashSet<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            Integer count = map.getOrDefault(num, 0) + 1;
            map.put(num, count);
            if (count > threshold) {
                res.add(num);
            }
        }
        return new LinkedList<>(res);
    }


    /**
     *
     * 方法二：摩尔投票法
     * 背景知识
     *
     * 摩尔投票法：摩尔投票法的核心思想为对拼消耗。首先我们考虑最基本的摩尔投票问题，比如找出一组数字序列中出现次数大于总数二分之一的数字（并且假设这个数字一定存在）。
     * 我们可以直接利用反证法证明这样的数字只可能有一个。摩尔投票算法的核心思想是基于这个事实：
     *
     * 每次从序列里选择两个不相同的数字删除掉（或称为「抵消」），最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个元素。
     * 假设我们当前数组中存在次数大于总数一半的元素为 x，数组的总长度为 n，
     * 则我们可以把数组分为两部分，
     * 一部分为相同的 k 个元素 x，
     * 另一部分为 二分之（n-k）对个不同的元素配对，
     *
     * 此时我们假设还存在另外一个次数大于总数一半的元素 y，则此时 y 因该满足 y大于二分之n，但是按照我们之前的推理 y 应当满足 y≤二分之（n-k），二者自相矛盾。
     *
     *
     * 解题思路
     *
     * 题目要求找出其中所有出现超过 n/3 次的元素。我们可以利用反证法推断出满足这样条件的元素最多只有两个，
     * 我们可以利用摩尔投票法的核心思想，每次选择三个互不相同的元素进行删除（或称为「抵消」）。
     *
     * 我们可以假设数组中一定只存在一个次数大于  n/3的元素 x，其中 n 为数组的长度，
     * 则此时我们可以把数组分成两部分：
     * 一部分相同的 k 个元素 x，
     * 另一部分为 三分之（n-k）组三个不同的元素，我们知道三个不同的元素会被抵消，因此最终只会剩下一个元素为 x。
     *
     * 如果只存在 2 个次数大于 三分之n 的元素时，我们假设这两个不同的元素分别为 x 和 y，
     * 则此时我们一定可以把数组分成三部分：
     * 第一部分相同的 m 个元素 x，
     * 第二部分相同的 k 个元素 y，
     * 第三部分为 三分之（n-m-k）组三个互不同的元素，我们知道三个互不同的元素会被抵消，因此最终只会剩下两个元素为 x 和 y。
     *
     * 我们每次检测当前元素是否为第一个选中的元素或者第二个选中的元素。
     *
     * 每次我们发现当前元素与已经选中的两个元素都不相同，则进行抵消一次。
     *
     * 如果存在最终选票大于 000 的元素，我们还需要再次统计已选中元素的次数,检查元素的次数是否大于 三分之n
     *
     * @param nums
     * @return
     */
    public List<Integer> majorityElement3(int[] nums) {
        int element1 = 0;
        int element2 = 0;
        int vote1 = 0;
        int vote2 = 0;

        for (int num : nums) {
            if (vote1 > 0 && num == element1) { //如果该元素为第一个元素，则计数加1
                vote1++;
            } else if (vote2 > 0 && num == element2) { //如果该元素为第二个元素，则计数加1
                vote2++;
            } else if (vote1 == 0) { // 选择第一个元素
                element1 = num;
                vote1++;
            } else if (vote2 == 0) { // 选择第二个元素
                element2 = num;
                vote2++;
            } else { //如果三个元素均不相同，则相互抵消1次
                vote1--;
                vote2--;
            }
        }

        int cnt1 = 0;
        int cnt2 = 0;
        for (int num : nums) {
            if (vote1 > 0 && num == element1) {
                cnt1++;
            }
            if (vote2 > 0 && num == element2) {
                cnt2++;
            }
        }
        // 检测元素出现的次数是否满足要求
        List<Integer> ans = new ArrayList<>();
        if (vote1 > 0 && cnt1 > nums.length / 3) {
            ans.add(element1);
        }
        if (vote2 > 0 && cnt2 > nums.length / 3) {
            ans.add(element2);
        }

        return ans;
    }


    /**
     * 本题是在任意多的候选人中，选出票数超过⌊ 1/3 ⌋的候选人。
     * 这意味着最多只能有两位候选人，反证:若候选人数m>2，则 由每名候选人的最小票数 x>n/3，求和得候选人总票数>mx>3n/3=n，即候选人的总票数超过了所有投票数，矛盾。
     * 可以这样理解，假设投票是这样的 [A, B, C, A, A, B, C]，ABC 是指三个候选人。
     *
     * 第 1 张票，第 2 张票和第3张票进行对坑，如果票都不同，则互相抵消掉；
     * 第 4 张票，第 5 张票和第 6 张票进行对坑，如果有部分相同，则累计增加他们的可抵消票数，如 [A, 2] 和 [B, 1]；
     * 接着将 [A, 2] 和 [B, 1] 与第 7 张票进行对坑，如果票都没匹配上，则互相抵消掉，变成 [A, 1] 和 [B, 0] 。
     * @param nums
     * @return
     */
    public List<Integer> majorityElement(int[] nums) {
        // 创建返回值
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        // 初始化两个候选人candidate，和他们的计票
        int cand1 = nums[0], count1 = 0;
        int cand2 = nums[0], count2 = 0;

        // 摩尔投票法，分为两个阶段：配对阶段和计数阶段
        // 配对阶段
        for (int num : nums) {
            // 投票
            if (cand1 == num) {
                count1++;
                continue;
            }
            if (cand2 == num) {
                count2++;
                continue;
            }

            // 第1个候选人配对
            if (count1 == 0) {
                cand1 = num;
                count1++;
                continue;
            }
            // 第2个候选人配对
            if (count2 == 0) {
                cand2 = num;
                count2++;
                continue;
            }

            count1--;
            count2--;
        }

        // 计数阶段
        // 找到了两个候选人之后，需要确定票数是否满足大于 N/3
        count1 = 0;
        count2 = 0;
        for (int num : nums) {
            if (cand1 == num) count1++;
            else if (cand2 == num) count2++;
        }

        if (count1 > nums.length / 3) res.add(cand1);
        if (count2 > nums.length / 3) res.add(cand2);

        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
